import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

    public static String nextLine() throws IOException {
        return br.readLine();
    }

    public static boolean hasNext() throws IOException {
        return br.ready();
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }


    static int n,m;
    static int[] dis;
    static int[][] g;
    static boolean[] is;
    static int[] h,w,e,ne;  // 接表的存储
    static int idx;

    public static void main(String[] args) throws IOException {
        n=nextInt();
        m=nextInt();

        dis=new int[n+1];





        h=new int[n+1];    //堆优化的dijkstra初始化，里面必需确定边的数量有多少
        w=new int[m+1];
        e=new int[m+1];
        ne=new int[m+1];
        Arrays.fill(h,-1);





        g=new int[n+1][n+1];   //朴素的dijkstra初始化
        is=new boolean[n+1];









        for(int i=0;i<=n;i++) Arrays.fill(g[i],0x3f3f3f3f);

        for (int i = 0; i < m; i++) {


            int a=nextInt();
            int b=nextInt();
            int c=nextInt();

            g[a][b]=Math.min(c,g[a][b]);  ////朴素的dijkstra初始化

            add(a,b,c);//堆优化的dijkstra初始化，


        }


         int[] cnt=new int[n+1];

        Arrays.fill(dis,(int)1e9);

        boolean[] is=new boolean[n+1];
        Queue<Integer> q=new LinkedList<>();
        for(int i=1;i<n;i++) {
            is[i]=true;
            q.add(i);
        }
        while(!q.isEmpty()) {

            int ver=q.poll();
            dis[2]=0;
            is[ver]=false;

            for(int i=h[ver];i!=-1;i=ne[i]){
                int j=e[i];

                if(dis[j]>dis[ver]+w[i]){
                    dis[j]=dis[ver]+w[i];
                    cnt[j]=cnt[ver]+1;

                    if(!is[j]){
                        q.add(j);
                        is[j]=true;
                    }
                }


            }



        }
        System.out.println(Arrays.toString(dis));
    }
    static void add(int a,int b,int c){
        w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;
    }


}





class Main1 {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static String next() throws IOException {
        while(st==null|| !st.hasMoreTokens()){
            st=new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

    public static String nextLine() throws IOException{
        return br.readLine();
    }

    public static boolean hasNext() throws IOException {
        return br.ready();
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long qpow(long a,long n){
        if(n==0) return 1;
        long ret=1;

        while(n>0){
            if((n&1)==1){
                ret*=a;
            }
            a*=a;
            n>>=1;
        }

        return ret;
    }

    public static long[][] initComb(int maxN){

        long[][] dp=new long[maxN+1][maxN+1];



        for(int i=0;i<=maxN;i++){
            dp[i][0]=1;
            for(int j=1;j<=i;j++){
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            }
        }

        return dp;

    }


    public static boolean[] sieve(int n){
        boolean[] isPrime=new boolean[n+1];

        Arrays.fill(isPrime,true);

        isPrime[0]=false;
        isPrime[1]=false;



        for(int i=2;i*i<=n;i++){
            if(isPrime[i]){
                for(int j=i*i;j<=n;j+=i){
                    isPrime[j]=false;
                }
            }

        }
        return isPrime;
    }

    class UnionFind{
        int[] parent;
        int[] rank;

        public UnionFind(int size){
            parent=new int[size];
            rank=new int[size];

            for(int i=0;i<size;i++) parent[i]=i;
        }

        public int find(int x){
            if(parent[x]!=x){
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }


        public void union(int x,int y){
            int rootX=find(x);
            int rootY=find(y);

            if(rootX!=rootY) {

                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    parent[rootX] = rootY;
                    if (rank[rootX] == rank[rootY]) {
                        rank[rootY]++;
                    }
                }
            }
        }
    }


//    class UnionFind {
//        int[] parent;
//        int[] rank;
//
//        public UnionFind(int size) {
//            parent = new int[size];
//            rank = new int[size];
//            for (int i = 0; i < size; i++) {
//                parent[i] = i;
//            }
//        }
//
//        public int find(int x) {
//            if (parent[x] != x) {
//                parent[x] = find(parent[x]);  // 路径压缩
//            }
//            return parent[x];
//        }
//
//        public void union(int x, int y) {
//            int rootX = find(x);
//            int rootY = find(y);
//            if (rootX != rootY) {
//                if (rank[rootX] > rank[rootY]) {  // 按秩合并
//                    parent[rootY] = rootX;
//                } else {
//                    parent[rootX] = rootY;
//                    if (rank[rootX] == rank[rootY]) {
//                        rank[rootY]++;
//                    }
//                }
//            }
//        }
//    }


    public static void main(String[] args) throws IOException {
//        System.out.println(qpow(2,4));
//        long[][] longs = initComb(10);
//        System.out.println(longs[4][2]);
//        System.out.println(longs[4][1]);
//        System.out.println(longs[5][2]);



    }
}
